"""
https://leetcode.cn/problems/multiply-strings/description/

43. 字符串相乘
已解答
中等
相关标签
premium lock icon
相关企业
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

 

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"
 

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

"""

from typing import List


class Solution:
    """
    类似加法模拟，此次是乘法模拟
    一个常识：如果a和b是个位数（0~9），则0<=a*b<=81<99
    """

    def multiply(self, num1: str, num2: str) -> str:
        
        def num_str_to_int(s:str):
            """ 个位数字符串转数字 """
            return ord(s)-ord('0')

        rev_num1=num1[::-1]
        rev_num2=num2[::-1]
        ns=[]
        for i1 in range(len(rev_num1)):
            for i2 in range(len(rev_num2)):
                acc=num_str_to_int(rev_num1[i1])*num_str_to_int(rev_num2[i2])
                bp=i1+i2
                if bp==len(ns):
                    ns.append(acc)
                else:
                    ns[bp]+=acc
        
        num_strs:List[str]=[]
        next_num=0
        for i,acc in enumerate(ns):
            acc+=next_num
            num_strs.append(str(acc%10))
            next_num=acc//10

        res_str=str(next_num)+''.join(num_strs[::-1])
        
        zero_idx=-1
        for i in range(len(res_str)-1):
            if res_str[i]=='0':
                zero_idx=i
            else:
                break

        return res_str[zero_idx+1:]
    
if __name__=='__main__':
    num1='123'
    num2='456'

    sol=Solution()
    res=sol.multiply(num1,num2)
    print(res)